import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:和为k的子数组
 * User: bjc
 * Date: 2025-11-19
 * Time: 12:47
 */
public class Test05_subarraySum {
    //暴力解法
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int ret = 0;

        for (int i = 0; i < n; i++) {
            int tmp = nums[i];
            if(tmp == k) ret++;
            for (int j = i+1; j < n; j++) {
                tmp = nums[j] + tmp;
                if(tmp == k) ret++;
            }
        }
        return ret;
    }
    //使用前缀和+哈希表
    public int subarraySum1(int[] nums, int k) {
        //<前缀和，次数>
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1); //前缀和为0，出现次数为1。也就是说整个数组长度为k
        int sum = 0; //表示0-i位置的前缀和
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i]; //当前位置的前缀和
            ret += hash.getOrDefault(sum - k, 0); //从哈希表中查找是否有满足条件的前缀和
            hash.put(sum, hash.getOrDefault(sum, 0) + 1); //把当前的前缀和放到哈希表中
        }
        return ret;
    }
}
